#pragma once
#include <vector>
#include <memory>
#include <unordered_map>
#include <functional>
#include <cmath>

#include "include/PinPolygon.h"

// 网格单元类
class GridCell {
public:
    GridCell(int x, int y, double cellSize)
        : m_x(x), m_y(y), m_cellSize(cellSize) {
        m_bbox[0] = x * cellSize;      // minX
        m_bbox[1] = y * cellSize;      // minY
        m_bbox[2] = (x + 1) * cellSize; // maxX
        m_bbox[3] = (y + 1) * cellSize; // maxY
    }

    // 检查点是否在网格内
    bool contains(const Point& point) const {
        return point.x >= m_bbox[0] && point.x <= m_bbox[2] &&
            point.y >= m_bbox[1] && point.y <= m_bbox[3];
    }

    // 检查线段是否与网格相交
    bool intersects(const Line& line) const {
        // 使用Cohen-Sutherland算法进行线段裁剪测试
        int code1 = computeCohenSutherlandCode(line.Pt1);
        int code2 = computeCohenSutherlandCode(line.Pt2);

        // 完全在内部
        if (code1 == 0 && code2 == 0) return true;

        // 完全在外部
        if ((code1 & code2) != 0) return false;

        // 需要进一步检查相交
        return true;
    }

    // 检查多边形是否与网格相交（外包盒测试）
    bool intersects(const PinPolygon* polygon) const {
        // 外包盒快速测试
        if (polygon->m_box[2] < m_bbox[0] || polygon->m_box[0] > m_bbox[2] ||
            polygon->m_box[3] < m_bbox[1] || polygon->m_box[1] > m_bbox[3]) {
            return false;
        }

        // 详细边相交测试
        for (const auto& edge : polygon->m_edges) {
            if (intersects(edge)) {
                return true;
            }
        }

        return false;
    }

    // 添加多边形到网格
    void addPolygon(PinPolygon* poly) {
        // 检查是否与现有多边形相交
        
        m_polys.emplace_back(poly);
    }

    // 获取网格中的所有多边形
    const std::vector<PinPolygon*>& getPolygons() const {
        return m_polys;
    }

    // 获取网格边界
    const std::vector<double>& getBBox() const {
        return m_bbox;
    }

    int getX() const { return m_x; }
    int getY() const { return m_y; }

private:
    // Cohen-Sutherland算法编码
    int computeCohenSutherlandCode(const Point& point) const {
        int code = 0;
        if (point.x < m_bbox[0]) code |= 1;   // 左
        if (point.x > m_bbox[2]) code |= 2;   // 右
        if (point.y < m_bbox[1]) code |= 4;   // 下
        if (point.y > m_bbox[3]) code |= 8;   // 上
        return code;
    }

private:
    int m_x, m_y;
    double m_cellSize;
    std::vector<double> m_bbox = { 0, 0, 0, 0 }; // minX, minY, maxX, maxY
    std::vector<PinPolygon*> m_polys;
};


// 网格管理器类
class GridManager {
public:
    GridManager(double minX, double minY, double maxX, double maxY, double cellSize = 1)
        : m_minX(minX), m_minY(minY), m_maxX(maxX), m_maxY(maxY), m_cellSize(cellSize) {
        
        // 计算网格数量
        m_numCellsX = static_cast<int>(std::ceil((maxX - minX) / cellSize));
        m_numCellsY = static_cast<int>(std::ceil((maxY - minY) / cellSize));
        // 初始化网格
        m_gridCells.resize(m_numCellsX * m_numCellsY);
        for (int y = 0; y < m_numCellsY; ++y) {
            for (int x = 0; x < m_numCellsX; ++x) {
                m_gridCells[y * m_numCellsX + x] = std::make_unique<GridCell>(x, y, cellSize);
            }
        }
    }
   
    // 添加多边形到相应的网格
    void addPolygon(PinPolygon* poly) {
        // 获取多边形外包盒
        double minX = poly->m_box[0];
        double minY = poly->m_box[1];
        double maxX = poly->m_box[2];
        double maxY = poly->m_box[3];

        // 计算覆盖的网格范围
        int startX = std::max(0, static_cast<int>((minX - m_minX) / m_cellSize));
        int startY = std::max(0, static_cast<int>((minY - m_minY) / m_cellSize));
        int endX = std::min(m_numCellsX - 1, static_cast<int>((maxX - m_minX) / m_cellSize));
        int endY = std::min(m_numCellsY - 1, static_cast<int>((maxY - m_minY) / m_cellSize));

        // 添加到所有相交的网格
        for (int y = startY; y <= endY; ++y) {
            for (int x = startX; x <= endX; ++x) {
                GridCell* cell = getCell(x, y);
                if (cell && cell->intersects(poly)) {
                    cell->addPolygon(poly);
                }
            }
        }
    }

    // 获取指定坐标的网格
    GridCell* getCell(int x, int y) const {
        if (x < 0 || x >= m_numCellsX || y < 0 || y >= m_numCellsY) {
            return nullptr;
        }
        return m_gridCells[y * m_numCellsX + x].get();
    }

    // 获取包含点的网格
    GridCell* getCellAtPoint(const Point& point) const {
        int x = static_cast<int>((point.x - m_minX) / m_cellSize);
        int y = static_cast<int>((point.y - m_minY) / m_cellSize);
        return getCell(x, y);
    }

    // 获取线段经过的所有网格
    void getCellsAlongLine(const Line& line, std::vector<GridCell*>& cells) const {
        Point start = line.Pt1;
        Point end = line.Pt2;

        // 使用Bresenham算法遍历网格
        int x0 = static_cast<int>((start.x - m_minX) / m_cellSize);
        int y0 = static_cast<int>((start.y - m_minY) / m_cellSize);
        int x1 = static_cast<int>((end.x - m_minX) / m_cellSize);
        int y1 = static_cast<int>((end.y - m_minY) / m_cellSize);

        int dx = std::abs(x1 - x0);
        int dy = std::abs(y1 - y0);
        int sx = (x0 < x1) ? 1 : -1;
        int sy = (y0 < y1) ? 1 : -1;
        int err = dx - dy;

        while (true) {
            if (GridCell* cell = getCell(x0, y0)) {
                cells.emplace_back(cell);
            }

            if (x0 == x1 && y0 == y1) break;

            int e2 = 2 * err;
            if (e2 > -dy) {
                err -= dy;
                x0 += sx;
            }
            if (e2 < dx) {
                err += dx;
                y0 += sy;
            }
        }

        return;
    }

    // 获取所有网格
    const std::vector<std::unique_ptr<GridCell>>& getAllCells() const {
        return m_gridCells;
    }
     
private:
    double m_minX, m_minY, m_maxX, m_maxY;
    double m_cellSize;
    int m_numCellsX, m_numCellsY;
    std::vector<std::unique_ptr<GridCell>> m_gridCells;
   
};